package com.ma.graph;

import java.util.LinkedList;
import java.util.List;

/*
    输入：numCourses = 2, prerequisites = [[1,0]]
    输出：true
    解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。

    当存在循环依赖时，即当存在环时，false


 */
public class Solution297 {

    boolean[] isVisited;
    boolean[] onPath;
    boolean hasCycle;

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<Integer>[] graph = buildGraph(numCourses, prerequisites);
        //不一定所有节点都相连，遍历所有节点做DFS
        isVisited = new boolean[numCourses];
        onPath = new boolean[numCourses];
        for (int i = 0; i < numCourses; i++) {
            if(!isVisited[i]){

                traverse(graph, i);
            }
        }
        return !hasCycle;
    }

    void traverse(List<Integer>[] graph, int s) {
        if (onPath[s]) {
            //出现环
            hasCycle = true;
        }
        if (isVisited[s] || hasCycle) {
            // 已经找到环就不必再遍历了
            return;
        }
        //前序遍历位置
        isVisited[s] = true;
        onPath[s] = true;
        for (int t : graph[s]) {
            traverse(graph, t);
        }

        // 后序遍历位置
        onPath[s] = false;

    }

    //造图函数
    private List<Integer>[] buildGraph(int numCourses, int[][] prerequisites) {
        List<Integer>[] graph = new LinkedList[numCourses];
        for (int i = 0; i < numCourses; i++) {
            graph[i] = new LinkedList<>();
        }
        for (int[] edge : prerequisites) {
            int from = edge[1];
            int to = edge[0];
            graph[from].add(to);
        }
        return graph;
    }

    /**
     * 输入：numCourses = 2, prerequisites = [[1,0],[0,1]]
     * 输出：false
     * 解释：总共有 2 门课程。学习课程 1 之前，你需要先完成​课程 0 ；并且学习课程 0 之前，你还应先完成课程 1 。这是不可能的。.
     * <p>
     * 输入：numCourses = 2, prerequisites = [[1,0]]
     * 输出：true
     */
    public static void main(String[] args) {
        int numCourses = 2;
        int[][] prerequisites = {{1, 0}, {0, 1}};

        Solution297 solution = new Solution297();
        boolean b = solution.canFinish(numCourses, prerequisites);
        System.out.println(b);

    }
}
